Orden parcial completo

En matemáticas, el concepto orden parcial completo se usa para referirse al menos a tres clases de conjunto parcialmente ordenado similares, pero distintas, caracterizadas por propiedades de completitud. Los órdenes parciales completos desempeñan un papel principal en la informática teórica, en semántica denotacional y teoría de dominios.

Definiciones

Un orden parcial completo (abreviado opc) puede, según el contexto, referirse a cualquiera de los siguientes conceptos:

• Un conjunto parcialmente ordenado es un orden parcial dirigido completo ('opdc' ) si cada uno de sus subconjuntos dirigidos tiene un supremo. Un subconjunto de un orden parcial es dirigido si no está vacío y cada par de elementos tiene un límite superior en el subconjunto. En la teoría, los dcpos a veces también aparecen bajo la etiqueta pos-up-complete.

• Un conjunto parcialmente ordenado es un orden parcial dirigido-completo apuntado si es un opcd con un elemento mínimo. A veces se abrevia opdca.

• Un conjunto parcialmente ordenado es un ω-orden parcial completo (ω-opc) si es un orden parcialmente ordenado en el que cada ω-cadena (x₁≤x₂≤x₃≤x₄≤...) tiene un supremo que pertenece al conjunto subyacente del conjunto. Cada opcd es un ω-opc, ya que cada cadena ω es un conjunto dirigido, pero lo contrario no es cierto. Sin embargo, cada ω-opc con una base también es un opcd (con la misma base).​ Un ω-opc (opcd) con una base también se denomina ω-opc continuo(opcd continuo).

Téngase en cuenta que orden parcial completo nunca se usa para referirse a un orden parcialmente ordenado en el que todos los subconjuntos tienen máximo; la terminología retículo completo se utiliza para designar este concepto.

El requerimiento de la existencia de máximo dirigido puede motivarse al ver los conjuntos dirigidos como secuencias de aproximación generalizadas y el máximo como "límites" de los respectivos cálculos (aproximativos). Esta intuición, en el contexto de la semántica denotacional, fue la motivación detrás del desarrollo de teoría de dominios.

El concepto de dualidad de un conjunto parcialmente ordenado completo dirigido se denomina 'orden parcial completo filtrado. Sin embargo, este concepto aparece con mucha menos frecuencia en la práctica, ya que generalmente se puede trabajar explícitamente en el orden dual.

Ejemplos

• Cada orden parcialmente ordenado finito se dirige completo.
• Todas los retículos completos también se dirigen completos.
• Para cualquier cpo, el conjunto de todos los filtros no vacíos, ordenados por inclusión de subconjuntos, es un opcd. Junto con el filtro vacío también es dirigido. Si el orden tiene uniones binarias, entonces esta construcción (incluido el filtro vacío) en realidad produce un retículo completo.
• El conjunto de todas las funciones parciales en un conjunto dado S se puede ordenar definiendo f ≤ g para las funciones f y gsi y solo si g extiende f, es decir, si el dominio de f es un subconjunto del dominio de g y los valores de f y g coinciden en todas las entradas para las que se definen ambas funciones. (De manera equivalente, f ≤ g si y solo si f ⊆ g donde f y g son identificados con sus respectivos gráficas.) Este orden es un opcd señalado, donde el elemento más pequeño es la función definida en ninguna parte (con dominio vacío). De hecho, ≤ también es delimitado completo. Este ejemplo también demuestra por qué no siempre es natural tener un elemento mayor.
• El orden de especialización de cualquier espacio sobrio es un opcd.
• Se usa el término sistema deductivo como un conjunto de oraciones cerradas en consecuencia (para definir la noción de consecuencia, utilícese, por ejemplo, el enfoque algebraico de Tarski).​​ Hay teoremas interesantes que se refieren a un conjunto de sistemas deductivos que son una ordenación parcial dirigida completa.​ También, se puede elegir un conjunto de sistemas deductivos para tener un elemento mínimo de manera natural (para que pueda ser también un opcd apuntado), porque el conjunto de todas las consecuencias del conjunto vacío (es decir, "el conjunto de las oraciones lógicamente demostrables / lógicamente válidas") es (1) un sistema deductivo (2) contenido por todos los sistemas deductivos.

Propiedades

Un conjunto ordenado P es un opcd apuntado si y solo si cada cadena tiene un supremo en P, es decir, P es una cadena completa.​ Alternativamente, un conjunto ordenado P es un opcd apuntado si y solo si cada automapa de P tiene al menos punto fijo. Cada conjunto S se puede convertir en un opcd apuntado agregando un elemento mínimo ⊥ e introduciendo un orden plano con ⊥ ≤ s y s ≤ s para cada s ∈ S y ninguna otra relación de orden.

Funciones continuas y puntos fijos

Una función f entre dos opcds P y Q se llama Scott continua si aplica conjuntos dirigidos en conjuntos dirigidos mientras se conserva su supremo:

• $f(D)\subseteq Q$ es dirigido para cada $D\subseteq P$ dirigido.
• $f(\sup D)=\sup f(D)$ para cada $D\subseteq P$ dirigido.

Tenga en cuenta que cada función continua entre opcds es una función monótona. Esta noción de continuidad es equivalente a la continuidad topológica inducida por la topología de Scott.

El conjunto de todas las funciones continuas entre dos opcds P y Q se denota [P → Q]. Equipado con el orden puntual, esto es de nuevo un opcd, y un opc siempre que Q sea un opc. Así, los órdenes parciales completos con mapas continuos de Scott forman una categoría cartesiana cerrada.​

Cada auto-mapa de conservación de orden f de un opc ( P , ⊥) tiene un punto de corrección mínimo.​ Si f es continuo, este punto de referencia es igual al supremo de la función iterada (⊥, f (⊥), f (f (')), ...fⁿ ( ⊥),…) de ⊥ (consúltese también el teorema de punto de referencia de Kleene).

Véase también

La completitud dirigida se relaciona de varias maneras con otras nociones de completitud, tales como el orden parcial de cadena completa. La completitud dirigida por sí sola es una propiedad bastante básica que se da a menudo en otras investigaciones teóricas sobre el orden, utilizando, por ejemplo, conjuntos algebraicos parcialmente ordenados y la topología de Scott.

Bibliografía

• Davey, B.A.; Priestley, H. A. (2002). Introduction to Lattices and Order (Second edición). Cambridge University Press. ISBN 0-521-78451-4. 

• Datos: Q3082805